#define  _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
//乘积最大子数组
//为数不多的独自oj的题目，首先大体框架思路延续了子数组问题的框架
//然后没想太多当然是没有过，看到错误事例的时候发现没有考虑负数，符号变换的这一情况，也就是符号一变，最大值可能是最小值，最小值可能是最大值
//到这里只要充分理解这句话就可以了，变成了一个多状态的dp问题，好在之前接触过
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int n = nums.size();
        //创建dp表
        vector<int> f(n), g(n);

        //初始化
        f[0] = g[0] = nums[0];
        //填表
        int ret = INT_MIN;

        for (int i = 1; i < n; i++)
        {
            f[i] = max(f[i - 1] * nums[i], max(nums[i], g[i - 1] * nums[i]));
            g[i] = min(g[i - 1] * nums[i], min(nums[i], f[i - 1] * nums[i]));
        }


        //返回值
        for (int i = 0; i < n; i++)  ret = max(ret, f[i]);
        return ret;

    }
};


int main()
{

	return 0;
}